package jobs.job1.map;
import java.util.Objects;
/*
简易版本的hash-map
1.数据结构 使用 数组+链表 实现
2.数组的大小n只能是2的k次方，以便可以通过hash & n - 1 的方式来确定key的索引
3.因为数组的最大容量为2^31-1，所以数组的最大容量为2^30
4.装载因子设置为0.75，参考官方源码，每个碰撞位置的链表长度超过８个是概率非常低。
5.数组第一次扩容的基础大小，并不是0、1、2、4、8...的过渡，而是直接以16做为基础容量开始
6.扩容算法，需要将存放在老的数组中的元素迁移到新数组中，可以简单的通过遍历每一个元素计算在新数组中的索引来迁移，
但也可以使用一个高效算法，将链表拆分成两部分分别迁移。具体见迁移算法注释。
7.实现了get、put、resize 3个方法。
 */
public class MyHashMap<K, V> {

    //  hash-map底层储存使用的数据结构--数组
    @SuppressWarnings("unchecked")
    private Node<K, V>[] table = new Node[0];//使用长度为0的数组，优化判空处理的代码
    private int threshold = 0;//当数组中储存的元素超过该值，将执行resize扩容，该值被设置为 数组容量大小 × 装载因子
    private int size = 0;//记录table数组的使用量

    // 根据key获取对应的value
    public V get(K key) {
        if (table.length == 0) return null;     //空hash-map，没有储存任何值
        final int capacity = table.length;      //获得当前数组的容量，一定是2的k次方
        final int hash = hash(key);             //计算key的hash值
        final int index = hash & capacity - 1;  //根据hash值计算元素在数组中的索引位置
        Node<K, V> p = table[index];            //获取该位置链表的头节点
        while (p != null) {                     //遍历链表p找到匹配的key，并返回value
            if (hash == p.hash && (Objects.equals(key, p.key)))  //如果key一样，则找到了对应的value
                return p.value;
            p = p.next;
        }
        return null;
    }

    //  储存key-value对，如果key已经存在，则更新且返回原来的值，否则返回null
    public V put(K key, V value) {
        if (table.length == 0) table = resize();            //扩容
        final int capacity = table.length;                  //获得当前数组的容量，一定是2的k次方
        final int hash = hash(key);                         //计算key的hash值
        final int index = hash & capacity - 1;              //根据hash值计算元素在数组中的索引位置
        Node<K, V> p = table[index];                        //获取该位置链表的头节点
        if (p == null) {                                    //如果该位置为空
            p = new Node<>(hash, key, value);               //创建一个新的节点，作为链表的头节点
            table[index] = p;                               //并直接储存在数组中
            size++;
            return null;                                    //原key-value对不存在，因此返回null
        }
//      解决hash冲突
        while (p != null) {                                 //遍历链表，
            if (hash == p.hash && (Objects.equals(key, p.key))) {
                //一旦发现key与当前节点key的hash相同，并且key相同或者内容相同，
                //那么说明该key对应的value已经存在，则更新
                V oldValue = p.value;
                p.value = value;
                return oldValue;//返回旧值
            }
            p = p.next;
        }
//      循环结束，则说明key是一个新key，需要添加
        Node<K, V> newNode = new Node<>(hash, key, value);      //创建新节点并添加到链表的头部
        newNode.next = table[index];
        table[index] = newNode;
        if (++size > threshold)                                 //如果table数组的使用量超过阈值
            resize();                                           //则进行扩容
        return null;                                            //原key-value对不存在，因此返回null
    }


//    扩容算法
    private Node<K, V>[] resize() {
        final int oldCap = table.length;
        final int oldThr = threshold;
        int newCap;
        int newThr;
        if (oldCap == 0) {//首次扩容
            newCap = DEFAULT_INITIAL_CAPACITY;//数组第一次扩容的基础大小，并不是0、1、2、4、8...的过渡，而是直接以16做为基础容量开始
            newThr = (int) (newCap * DEFAULT_LOAD_FACTOR);//得到扩容阈值
        } else {
            if (oldCap >= MAXIMUM_CAPACITY) {//如果容量已经达到最大值2^30次方，则无法继续进行扩容。
                threshold = Integer.MAX_VALUE;//修改阈值为最大整数值，以后将不可能触发扩容条件
                return table;//无法继续进行扩容,直接返回
            } else {
                newCap = oldCap << 1;//以2的倍数进行扩容
                newThr = oldThr << 1;//阈值也一样，能满足 thr = cap × 0.75
            }
        }
        threshold = newThr;//设置新阈值
        @SuppressWarnings("unchecked")
        Node<K, V>[] newTab = new Node[newCap];//创建扩容后的数组
//        接下来需要将储存在旧数组中的元素插入到新的数组中
        for (int i = 0; i < oldCap; i++) {
            Node<K, V> p = table[i];//遍历旧数组
            if (p != null) {//如果该位置存有元素，则进行迁移
                if (p.next == null) {//因为该位置的元素是链表类型储存的，如果链表长度为1，则迁移单个元素
                    newTab[p.hash & newCap - 1] = p;//重新计算该元素在新数组中的位置,并储存之
                } else {
//              否则链表长度大于1，则使用一个迁移算法，将原链表拆分成2个链表，A链表和B链表
//              其中A链表中的元素储存在新数组中的索引不需要发生改变，
//              B链表中的元素在新数组中的索引只需要在原来的索引值基础上加上oldCap
//              因为根据index = hash & (oldCap - 1) 算法，确定元素在数组中的索引，
//              新数组的容量翻倍，因此公式可写成 index = hash & (2 × oldCap - 1)
//              因为hash是没有改变的，且oldCap是2的k次方。因此新的索引在原来的基础上只多了一个高位值
//              如果hash值的该位为0，则索引没有发生变化，如果为1，则需要在索引的基础上加上oldCap值。
                    Node<K, V> A = null;//链表A
                    Node<K, V> ATail = null;//用于跟踪链表A最后一个元素
                    Node<K, V> B = null;//链表B
                    Node<K, V> BTail = null;//用于跟踪链表B最后一个元素
                    while (p != null) {//遍历链表
                        if ((p.hash & oldCap) == 0) {//如果增加的高位值为0，则该元素储存在新数组中的位置不需要发生改变，放入A链表
                            if (A == null) A = p;
                            else ATail.next = p;        //添加到链表A尾部
                            ATail = p;                  //跟踪链表A最后一个元素
                        } else {                        //否则放入B链表
                            if (B == null) B = p;
                            else BTail.next = p;        //添加到链表B尾部
                            BTail = p;                  //跟踪链表B最后一个元素
                        }
                        p = p.next;
                    }
//                    现在链表p被拆分成A和B两个链表
                    if (A != null) {
                        ATail.next = null;
                        newTab[i] = A;//链表A中的元素存放在数组中的索引不需要发生改变，和在旧数组中的位置一致。
                    }
                    if (B != null) {
                        BTail.next = null;
                        newTab[i + oldCap] = B;//链表B 中的元素存放在数组中的索引需要加上老的容量大小，因为hash高位值为1
                    }
                }
            }
        }
        return table = newTab;
    }

    //    组成链表的数据结构--节点
    static class Node<K, V> {
        //        key 的散列值
        final int hash;
        //      储存key
        final K key;
        //        储存value
        V value;
        //        用于记录下一个节点
        Node<K, V> next;

        public Node(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }
    //     计算key的hash值，通过异或运算计算出来的hash比较均匀，不容易出现冲突。这里也没验证过
    private static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

//  常量
    private static final int MAXIMUM_CAPACITY = 1 << 30;//数组的最大容量为2^30
    private static final int DEFAULT_INITIAL_CAPACITY = 16;//数组第一次扩容的基础大小，并不是0、1、2、4、8...的过渡，而是直接以16做为基础容量开始
    private static final double DEFAULT_LOAD_FACTOR = 0.75f;//默认的装载因子为0.75

//    测试MyHashMap
    public static void main(String[] args) {

        MyHashMap<String, Object> myHashMap = new MyHashMap<>();
        System.out.println(myHashMap.size + "," + myHashMap.table.length);
        for (int i = 0; i < 25; i++) {
            myHashMap.put("key" + i, "value" + i);
            System.out.println(myHashMap.size + "," + myHashMap.table.length);
        }
        for (int i = 0; i < 26; i++) {
            System.out.println(myHashMap.get("key" + i));
        }
    }
}




